//
// test.go
// Copyright (C) 2022 crane <crane@his-pc>
//
// Distributed under terms of the MIT license.
//

package main

import (
	"fmt"
	"sort"
	"strconv"
)

// 2.Largest number
// 2.1 Given a list of non negative integers, arrange them such that they form the largest number. (You may implement your program in pseudocode or any programming language.)

//   Example:
//     (1). input: [10,2]          output: "210"
//     (2). input: [3,30,34,5,9]   output: "9534330"

// 2.2 Is it possible to improve the program?

func LargestNumber(in []int) string {
	sortedResults := sortByAlphaOrder(in) // 获得字典序

	resultStr := ""
	for _, n := range sortedResults {
		part := strconv.Itoa(n)
		resultStr += part + ","
	}

	return resultStr
}

// 计算字典倒序
func sortByAlphaOrder(origin []int) []int {
	// 直接借助一下golang 内置排序算法, 回调自己的比较方法.
	// 得到一个字典序排序

	sort.Slice(origin, func(i int, j int) bool {
		// 32 vs 3
		// [2, 3] vs [3]
		a := origin[i]
		b := origin[j]

		aDigits := number2Digits(a)
		bDigits := number2Digits(b)

		aLen := len(aDigits)
		bLen := len(bDigits)

		aIdx := aLen - 1
		bIdx := bLen - 1

		// 对二数的digit开始倒序比较
		endIdx := -1
		for aIdx != endIdx || bIdx != endIdx {
			if aIdx == endIdx {
				aIdx = aLen - 1
			}

			if bIdx == endIdx {
				bIdx = bLen - 1 // b 从头再来
			}

			aCurrent := aDigits[aIdx]
			bCurrent := bDigits[bIdx]

			if aCurrent > bCurrent {
				return true
			} else if aCurrent < bCurrent {
				return false
			}

			// 如果相等, 继续比较下一位
			aIdx -= 1
			bIdx -= 1
		}

		return false
	})

	return origin
}

// 获得一个整数的各个'位/digit'
// 123 ===>  [3, 2, 1]
func number2Digits(n int) []int {
	results := []int{}
	for n != 0 {
		results = append(results, n%10)

		n /= 10
	}

	return results
}

func main() {
	fmt.Println("largest number 10, 2 =", LargestNumber([]int{5, 3, 72, 7999, 2, 78, 1, 9, 7, 99, 8, 73}))
	fmt.Println("largest number 10, 2 =", LargestNumber([]int{123, 123123124}))
	//fmt.Println("largest number 10, 2 =", LargestNumber([]int{5, 3, 72, 7999, 2, 78, 1, 9, 7, 99, 8, 73}))
}
